/**
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
示例 3：
输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
 */
function merge(intervals) {
  intervals.sort((a,b) => a[0] - b[0]);
  let pre = intervals[0];
  let result = [];
  for(let i = 0;i<intervals.length;i++){
    let curr = intervals[i];
    if(curr[0] > pre[1]){
      result.push(pre);
      pre = curr;
    }else{
      pre[1] = Math.max(curr[1],pre[1]);
    }
  }
  result.push(pre);
  return result;
}
const intervals = [[1,3],[2,6],[8,10],[15,18]];
console.log(merge(intervals));
/**
idea: 贪心算法
先排序，一个指针指向当前区间，遍历区间，如果当前区间的开始时间大于前一个区间的结束时间，则将当前区间加入结果集，否则合并区间，更新前一个区间的结束时间。
 */